package dp;

import java.util.Scanner;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:：给你k种⾯值的硬币，⾯值分别为c1,c2	...	ck	，
 * 每种硬 币的数量⽆限，再给⼀个总⾦额amount，问你最少需要⼏枚硬币凑出这个⾦额，如果不可能凑出，算法返回-1	。
 * User:Mr.Du
 * Date:2020/9/11
 * Time:12:34
 */
public class Coins {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int amount = sc.nextInt();
        int[] coins = {1,2,5};

        int res = getAmount(amount, coins);
        System.out.println(res);
    }

    private static int getAmount(int amount, int[] coins) {
        int[] dp = new int[amount+1];
        for(int i = 0;i<dp.length;i++){
            dp[i] = amount+1;
        }
        dp[0] = 0;
        for(int i = 0;i<dp.length;i++){
            for (int coin : coins){
                if(i - coin < 0) continue;
                dp[i] = Math.min(dp[i],dp[i-coin]+1);
            }
        }
        return dp[amount] == amount+1 ? -1 : dp[amount];
    }
}
